package offer.day23;

import com.company.atguigu.Person;

import java.util.*;

public class No38Permutation {
    /*
     * 面试题38：字符串的排列
     * 题目：输入一个字符串，打印该字符串中字符的所有排列。
     * 例如：输入字符串abc，打印出字符a、b、c所能排列出来的所有字符串abc,acb,bac,bca,cab,cba
     *
     * 思路：将字符串的多个位置拆分成  ==> 第一个字符+其他字符
     * 第一步：第一个字符可以是字符串中的任意一个
     * 第二步：剩下的其他字符又可以拆成==> 第一个字符+其他字符
     * 。。。。
     * 以此类推  这是一个递归的过程
     * 分为两步实现：处理第一个字符
     * 			处理剩余字符 （使剩余字符中的第一个字符   重新作为   一个新的第一个字符）
     * 			。。。直到走到最后一个字符
     *
     * */
    public static void main(String[] args) {
        No38Permutation p = new No38Permutation();

        String s = "abc";
        String[] permutation = p.Permutation(s);
        System.out.println(Arrays.toString(permutation));

    }

    Set<String> set = new HashSet<>();

    public String[] Permutation(String s) {
        if (s.trim().length() == 0 || s == null) return new String[]{};
        boolean[] flag = new boolean[s.length()];
        process(s, "", flag);
        return set.toArray(new String[set.size()]);

    }

    private void process(String s, String str, boolean[] flag) {
        if (s.length() == str.length()) {
            set.add(str);
            return;
        }
        for (int i = 0; i < s.length(); i++) {
            char tmp = s.charAt(i);
            if (flag[i]) {
                continue;
            }
            flag[i] = true;
            process(s,str+String.valueOf(tmp),flag);
            flag[i]=false;
        }
    }


}
